#include <stdio.h>
#include <stdlib.h>
// 一条包含字母 A-2 的消息通过以下映射进行了 编码:
//      'A’->“1”
//      'B’->"2"
//      'Z’->“26
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母(可能有多种方法)。
// 例如，“11106”可以映射为:
//      · “AAJF”，将消息分组为(1110 6)
//      · “KTF”，将消息分组为(11106)
// 注意，消息不能分组为(11106)，因为“06”不能射为“F”，这是由于“6”和“06”在映射中并不等价。
// 给你一个只含数字的 非空 字符串 s，请计算并返回 解码 方法的 总数题目数据保证答案肯定是一个 32 位 的整数。

int main(){
    char s[] = "121212";
    int n = sizeof(s)/sizeof(s[0]) - 1;
    int *dp = (int*)malloc(n * sizeof(int));
    // 初始化
    dp[0] = 1;
    if(s[1]=='0'){
        dp[1] = 1;
    }else if((s[0]-'0')*10+(s[1]-'0') > 26){
        dp[1] = dp[0];
    }else{
        dp[1] = dp[0] + 1;
    }
    // 进行递推
    for(int i=2;i<n;i++){
        if(s[i] == '0'){
            dp[i] = dp[i-2];
        }else if(s[i-1] == '0' || (s[i-1]-'0')*10+(s[i]-'0') > 26){ // 判断两个数拼接能否解码
            dp[i] = dp[i-1];
        }else{
            dp[i] = dp[i-1] + dp[i-2];
        }
    }
    printf("%d",dp[n-1]);

    return 0;
}